package main

import "fmt"

func main() {
	t := []int{73, 74, 75, 71, 69, 72, 76, 73}
	fmt.Println(dailyTemperatures(t))
}

/*
解题思路：将今天的温度与栈顶那一天的温度进行比较，
如果比栈顶温度低或栈空则进栈，
比栈顶温度高则栈顶出栈，然后继续和现在的栈顶进行比较，直到比栈顶温度低或者栈空

栈中保存的是对应的下标值，通过下标获取某一天的温度，同时该下标可以用来计算下一次高温是几天后
*/

func dailyTemperatures(T []int) []int {
	var result []int
	// 栈中保存着T的下标，通过下标可以获取到T中对应的温度，这里的时间复杂度是O(1)
	var stack []int
	for key, value := range T {
		result = append(result, 0)
		if len(stack) == 0 {
			stack = append(stack, key)
		} else {
			stackTop := stack[len(stack)-1]
			for value > T[stackTop] {
				result[stackTop] = key - stackTop
				stack = stack[:len(stack)-1]
				if len(stack) == 0 {
					break
				}
				stackTop = stack[len(stack)-1]
			}
			// 将今天的温度下标压入栈中
			stack = append(stack, key)
		}
	}

	return result
}
